{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "bso-fs-action-reduce.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Neofly4023/bso-fs/blob/master/bso_fs_action_reduce.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "metadata": {
        "id": "LFFRO2qoAiLd",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Install dependencies\n",
        "This part is in case you run the book in local, because Colab environment already contains most of popular python packages for ML ( like numpy, pandas and sklearn )"
      ]
    },
    {
      "metadata": {
        "id": "pAUATBVpAdJ2",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "!pip install xlsxwriter pandas numpy sklearn matplotlib"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "qWW9zZvdAM8T",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Import dependencies\n",
        "This par contains all the dependencies that you need to import to run the notebook"
      ]
    },
    {
      "metadata": {
        "id": "mDIDsIGD-Zoq",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import os, glob, random, copy, sys, time, re, operator, xlsxwriter\n",
        "from collections import defaultdict\n",
        "from sklearn import metrics\n",
        "from sklearn.model_selection import train_test_split, cross_val_score, KFold, StratifiedKFold, \\\n",
        "ShuffleSplit\n",
        "from sklearn.neighbors import KNeighborsClassifier\n",
        "from sklearn.svm import SVC\n",
        "from sklearn.preprocessing import StandardScaler\n",
        "from oauth2client.client import GoogleCredentials\n",
        "from google.colab import drive"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "eumjpGmwA_k2",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Mounting your drive \n",
        "This part is to mount the drive and be able to save results in it"
      ]
    },
    {
      "metadata": {
        "id": "OzO3p0En-duq",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "gdrive_path = '/content/gdrive'\n",
        "drive.mount(gdrive_path)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "YUOiNscrBJdU",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Bee class\n",
        "This class is the implementation of the Bee Swarm Optimization bee"
      ]
    },
    {
      "metadata": {
        "id": "Ru5acK-e-igy",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class Bee :\n",
        "    def __init__(self,id,problem,locIterations,state):\n",
        "        self.id=id\n",
        "        self.data=problem\n",
        "        self.solution = Solution(self.data,state=state)\n",
        "        self.fitness= 0.0\n",
        "        self.rl_return = 0.0\n",
        "        self.locIterations=locIterations\n",
        "        self.action = []\n",
        "    \n",
        "    def localSearch(self):\n",
        "        best=self.fitness\n",
        "        #done=False\n",
        "        lista=[j for j, n in enumerate(self.solution.get_state()) if n == 1]\n",
        "        indice =lista[0]\n",
        "        \n",
        "        for itr in range(self.locIterations):\n",
        "            while(True):\n",
        "                pos = -1\n",
        "                oldFitness = self.fitness\n",
        "                for i in range(len(self.solution.get_state())):\n",
        "                    \n",
        "                    if ((len(lista)==1) and (indice==i) and (i < self.data.nb_attribs-1)):\n",
        "                        i+=1\n",
        "                    self.solution.state[i]= (self.solution.state[i] + 1) % 2\n",
        "                    quality = self.solution.get_accuracy(self.solution.get_state())\n",
        "                    \n",
        "                    if (quality > best):\n",
        "                        pos = i\n",
        "                        best = quality\n",
        "                    self.solution.state[i]= (self.solution.state[i]+1) % 2\n",
        "                    self.fitness = oldFitness \n",
        "                if (pos != -1):\n",
        "                    self.solution.state[pos]= (self.solution.state[pos]+1)%2\n",
        "                    self.fitness = best\n",
        "                else:\n",
        "                    break\n",
        "            for i in range(len(self.solution.get_state())):\n",
        "                oldFitness=self.fitness\n",
        "                if ((len(lista)==1) and (indice==i) and (i < self.data.nb_attribs-1)):\n",
        "                    i+=1\n",
        "                self.solution.state[i]= (self.solution.state[i] + 1) % 2\n",
        "                quality = self.solution.get_accuracy(self.solution.get_state())\n",
        "                if (quality<best):\n",
        "                    self.solution.state[i]= (self.solution.state[i] + 1) % 2\n",
        "                    self.fitness = oldFitness\n",
        "\n",
        "\n",
        "    def ql_localSearch(self,maxIterIndex,flip):\n",
        "      \n",
        "        \"\"\"The reason why we do this is to \n",
        "        explore at the beginning and \n",
        "        eploit at the end to converge to the optimal solution\"\"\"\n",
        "        iterations = int(maxIterIndex/self.locIterations)+1 if int(maxIterIndex/self.locIterations)+1 <= self.locIterations else self.locIterations\n",
        "        for itr in range(iterations):\n",
        "       \n",
        "          state = self.solution.get_state()\n",
        "          # We get the best solution to be calculated yet\n",
        "          best_state = Solution.get_best_sol()\n",
        "          # We xor ( logic xor ) it with the actual state we're in to define the actions that could be done\n",
        "          if best_state[1] != 0:\n",
        "            xor_states = Solution.xor(state,best_state[0])\n",
        "          else:\n",
        "            xor_states = Solution.xor(state,[0 for i in range(len(state))])\n",
        "\n",
        "          # We get the indexes of the actions to do and pass them to the step() function to pick the next state  \n",
        "          actions = Solution.get_indexes(xor_states)\n",
        "\n",
        "          #next_state, action = self.data.ql.step(self.solution,self.data.nb_attribs)\n",
        "          # Ths first +1, is not to devide by 0, the 2nd one, is not to get an empty list in case iterations > nb_atts\n",
        "          #next_state, action = self.data.ql.step(self.solution,int(self.data.nb_attribs/(iterations+1))+1)\n",
        "\n",
        "          next_state, action = self.data.ql.step(self.solution,actions,flip)\n",
        "          next_sol = Solution(self.data,state=next_state)\n",
        "          acc_state = self.solution.get_accuracy(state)\n",
        "          acc_new_state = self.solution.get_accuracy(next_state)\n",
        "\n",
        "          if (acc_state < acc_new_state):\n",
        "              reward = acc_new_state\n",
        "          elif (acc_state > acc_new_state):\n",
        "              reward = acc_new_state - acc_state\n",
        "          else :\n",
        "              if (Solution.nbrUn(state) > Solution.nbrUn(next_state) ):\n",
        "                  reward = 1/2 * acc_new_state\n",
        "              else :\n",
        "                  reward = -1/2 * acc_new_state\n",
        "\n",
        "          self.data.ql.learn(self.solution,action,reward,next_sol)\n",
        "          self.rl_return = self.data.ql.get_q_value(self.solution,action)\n",
        "          self.fitness = acc_new_state\n",
        "          self.solution = next_sol\n",
        "          #print(\"Next state's acc : \",acc_new_state)\n",
        "          #print(\"This is acc choosed : {0}\".format(acc_new_state))\n",
        "            \n",
        "    def setSolution(self,solution):\n",
        "        self.solution.set_state(solution)\n",
        "        self.fitness = self.solution.get_accuracy(solution)\n",
        "    \n",
        "    @classmethod\n",
        "    def Rand(self, num, start=None, end=None): \n",
        "        res = [] \n",
        "        if (not start) or (not end): \n",
        "          \"\"\"We used 20%/80% (Pareto's law) to initilize the solution\"\"\"\n",
        "          res = np.random.choice([0,1],size=(num,),p=[8./10,2./10]).tolist()\n",
        "        else: \n",
        "          for j in range(num): \n",
        "              res.append(random.randint(start, end))\n",
        "        return res "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "7Q1zHx0KBWNy",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Swarm class\n",
        "This class is the implementation of the Bee Swarm Optimization swarm"
      ]
    },
    {
      "metadata": {
        "id": "UCVpz2Fh-lT-",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class Swarm :\n",
        "    def __init__(self,problem,flip,maxChance,nbrBees,maxIterations,locIterations):\n",
        "        self.data=problem\n",
        "        self.flip=flip\n",
        "        self.maxChance=maxChance\n",
        "        self.nbChance=maxChance\n",
        "        self.nbrBees=nbrBees\n",
        "        self.maxIterations=maxIterations\n",
        "        self.locIterations=locIterations\n",
        "        self.beeList=[]\n",
        "        self.refSolution = Bee(-1,self.data,self.locIterations,Bee.Rand(self.data.nb_attribs))\n",
        "        self.bestSolution = self.refSolution\n",
        "        self.tabou=[]\n",
        "        self.feature_count = { i:0 for i in range(self.data.nb_attribs) }\n",
        "        Solution.solutions.clear()\n",
        "\n",
        "    def searchArea(self):    \n",
        "        i=0\n",
        "        h=0\n",
        "        \n",
        "        self.beeList=[]\n",
        "        while((i<self.nbrBees) and (i < self.flip) ) :\n",
        "            #print (\"First method to generate\")\n",
        "            \n",
        "            solution=self.refSolution.solution.get_state()\n",
        "            k=0\n",
        "            while((self.flip*k+h) < len(solution)):\n",
        "                solution[self.flip*k +h] = ((solution[self.flip*k+h]+1) % 2)\n",
        "                k+=1\n",
        "            newBee=Bee(i,self.data,self.locIterations,solution)\n",
        "            self.beeList.append(newBee)\n",
        "            \n",
        "            i+=1\n",
        "            h=h+1\n",
        "        h=0\n",
        "        \n",
        "        while((i<self.nbrBees) and (i< 2*self.flip )):\n",
        "            #print(\"Second method to generate\")\n",
        "\n",
        "            solution=self.refSolution.solution.get_state()\n",
        "            k=0\n",
        "            while((k<int(len(solution)/self.flip)) and (self.flip*k+h < len(solution))):\n",
        "                solution[int(self.data.nb_attribs/self.flip)*h+k] = ((solution[int(self.data.nb_attribs/self.flip)*h+k]+1)%2)\n",
        "                k+=1\n",
        "            newBee=Bee(i,self.data,self.locIterations,solution)\n",
        "            self.beeList.append(newBee)\n",
        "            \n",
        "            i+=1\n",
        "            h=h+1\n",
        "        while (i<self.nbrBees):\n",
        "            #print(\"Random method to generate\")\n",
        "            solution= self.refSolution.solution.get_state()\n",
        "            indice = random.randint(0,len(solution)-1)\n",
        "            solution[indice]=((solution[indice]+1) % 2)\n",
        "            newBee=Bee(i,self.data,self.locIterations,solution)\n",
        "            self.beeList.append(newBee)\n",
        "            i+=1\n",
        "        for bee in (self.beeList):\n",
        "            lista=[j for j, n in enumerate(bee.solution.get_state()) if n == 1]\n",
        "            if (len(lista)== 0):\n",
        "                bee.setSolution(Bee.Rand(self.data.nb_attribs))\n",
        "                \n",
        "    def selectRefSol(self):\n",
        "      self.beeList.sort(key=lambda Bee: Bee.fitness, reverse=True)\n",
        "      bestQuality=self.beeList[0].fitness\n",
        "      if(bestQuality>self.bestSolution.fitness):\n",
        "          self.bestSolution=self.beeList[0]\n",
        "          self.nbChance=self.maxChance\n",
        "          return self.bestSolution\n",
        "      else:\n",
        "          if(  (len(self.tabou)!=0) and  bestQuality > (self.tabou[len(self.tabou)-1].fitness)):\n",
        "              self.nbChance=self.maxChance\n",
        "              return self.bestBeeQuality()\n",
        "          else:\n",
        "              self.nbChance-=1\n",
        "              if(self.nbChance > 0): \n",
        "                  return self.bestBeeQuality()\n",
        "              else :\n",
        "                  return self.bestBeeDiversity()\n",
        "      \n",
        "    def distanceTabou(self,bee):\n",
        "        distanceMin=self.data.nb_attribs\n",
        "        for i in range(len(self.tabou)):\n",
        "            cpt=0\n",
        "            for j in range(self.data.nb_attribs):\n",
        "                if (bee.solution.get_state()[j] != self.tabou[i].solution.get_state()[j]) :\n",
        "                      cpt +=1\n",
        "            if (cpt<=1) :\n",
        "                return 0\n",
        "            if (cpt < distanceMin) :\n",
        "                distanceMin=cpt\n",
        "        return distanceMin\n",
        "    \n",
        "    def bestBeeQuality(self):\n",
        "        \n",
        "        distance = 0\n",
        "        i=0\n",
        "        pos=-1\n",
        "        while(i<self.nbrBees):\n",
        "            max_val=self.beeList[i].fitness\n",
        "            nbUn=Solution.nbrUn(self.beeList[i].solution.get_state())\n",
        "            while((i<self.nbrBees) and (self.beeList[i].solution.get_accuracy(self.beeList[i].solution.get_state()) == max_val)):\n",
        "                distanceTemp=self.distanceTabou(self.beeList[i])\n",
        "                nbUnTemp = Solution.nbrUn(self.beeList[i].solution.get_state())\n",
        "                if(distanceTemp > distance) or ((distanceTemp == distance) and (nbUnTemp < nbUn)):\n",
        "                    if((distanceTemp==distance) and (nbUnTemp<nbUn)):\n",
        "                        print(\"We pick the solution with less features\")\n",
        "                    nbUn=nbUnTemp\n",
        "                    distance=distanceTemp\n",
        "                    pos=i\n",
        "                i+=1\n",
        "            if(pos!=-1) :\n",
        "                return self.beeList[pos]\n",
        "        bee= Bee(-1,self.data,self.locIterations,Bee.Rand(self.data.nb_attribs))\n",
        "        return bee\n",
        "            \n",
        "    def bestBeeDiversity(self):\n",
        "        max_val=0\n",
        "        for i in range(len(self.beeList)):\n",
        "            if (self.distanceTabou(self.beeList[i])> max_val) :\n",
        "                max_val = self.distanceTabou(self.beeList[i])\n",
        "        if (max_val==0):\n",
        "            bee= Bee(-1,self.data,self.locIterations,Bee.Rand(self.data.nb_attribs))\n",
        "            return bee\n",
        "        i=0\n",
        "        while(i<len(self.beeList) and self.distanceTabou(self.beeList[i])!= max_val) :\n",
        "            i+=1\n",
        "        return self.beeList[i]\n",
        "    \n",
        "    def bso(self,typeOfAlgo,flip):\n",
        "        i=1\n",
        "        while(i<=self.maxIterations):\n",
        "            t1 = time.time()\n",
        "            #print(\"\\nrefSolution is : \", Solution.str_sol(self.refSolution.solution.get_state()))\n",
        "            self.tabou.append(self.refSolution)\n",
        "            print(\"BSO iteration N° : \",i)\n",
        "            \n",
        "            self.searchArea()\n",
        "\n",
        "            # The local search part\n",
        "            \n",
        "            for j in range(self.nbrBees):\n",
        "              if (typeOfAlgo == 0):\n",
        "                self.beeList[j].localSearch()\n",
        "              elif (typeOfAlgo == 1):\n",
        "                for episode in range(self.locIterations):\n",
        "                  self.beeList[j].ql_localSearch(i,flip)\n",
        "              self.count_features(self.beeList[j].solution.get_state())\n",
        "              print( \"Fitness of bee \" + str(j) + \" is : \" + str(self.beeList[j].fitness) + \"\\n\")\n",
        "            self.refSolution = self.selectRefSol()\n",
        "            t2 = time.time()\n",
        "            print(\"Time of iteration N°{0} : {1:.2f} s\\n\".format(i,t2-t1))\n",
        "            i+=1\n",
        "            \n",
        "        print(\"\\n[BSO parameters used]\\n\")\n",
        "        print(\"Type of algo : {0}\".format(typeOfAlgo))\n",
        "        print(\"Flip : {0}\".format(self.flip))\n",
        "        print(\"MaxChance : {0}\".format(self.maxChance))\n",
        "        print(\"Nbr of Bees : {0}\".format(self.nbrBees))\n",
        "        print(\"Nbr of Max Iterations : {0}\".format(self.maxIterations))\n",
        "        print(\"Nbr of Loc Iterations : {0}\\n\".format(self.locIterations))\n",
        "        print(\"Must 10% used features : \",self.best_features())\n",
        "        print(\"Best solution found : \",self.bestSolution.solution.get_state())\n",
        "        print(\"Accuracy of found sol : {0:.2f} \".format(self.bestSolution.fitness*100))\n",
        "        print(\"Number of features used : {0}\".format(Solution.nbrUn(self.bestSolution.solution.get_state())))\n",
        "        print(\"Size of solutions dict : {0}\".format(len(Solution.solutions)))\n",
        "        print(\"Average time to evaluate a solution : {0:.3f} s\".format(Solution.get_avg_time())) \n",
        "        print(\"Global optimum : {0}, {1:.2f}\".format(Solution.get_best_sol()[0],Solution.get_best_sol()[1]*100))\n",
        "        if (typeOfAlgo == 1):\n",
        "          print(\"Return (Q-value) : \",self.bestSolution.rl_return)  \n",
        "          #print(\"Total sorting time : {0:.2f} s\".format(Solution.sorting_time))\n",
        "        return self.bestSolution.fitness*100, Solution.nbrUn(self.bestSolution.solution.get_state())\n",
        "      \n",
        "      \n",
        "    def count_features(self,solution):\n",
        "        self.feature_count = {i:self.feature_count[i]+n for i, n in enumerate(solution)}\n",
        "\n",
        "    def best_features(self):\n",
        "        sorted_features = sorted(self.feature_count.items(), key=operator.itemgetter(1), reverse=True)\n",
        "        top_10 = round(0.1*self.data.nb_attribs)+1\n",
        "        best_features = sorted_features[:top_10]\n",
        "        return best_features"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "EbGzO9NBBgZv",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Solution class\n",
        "This class is the implementation of a solution, it contains attributs that a solution could have ( like the subset of featuresor the evaluation, to not train a model with the same subset of features each time ), it could be extensible to other attributs"
      ]
    },
    {
      "metadata": {
        "id": "AZnb2S8X-qBN",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "\n",
        "    solutions = {} \n",
        "    best_sol = None\n",
        "    tot_eval_time = 0\n",
        "    sorting_time = 0\n",
        "\n",
        "    def __init__(self,data,state):\n",
        "        self.data = data\n",
        "        self.state = state\n",
        "        self.accuracy = 0\n",
        "        self.solutions[Solution.str_sol(self.state)] = self.accuracy\n",
        "\n",
        "    def get_accuracy(self,state):\n",
        "        if (Solution.str_sol(state) in Solution.solutions):\n",
        "            if (Solution.solutions[Solution.str_sol(state)] == 0) :\n",
        "                self.set_accuracy(state)\n",
        "        else:\n",
        "          self.set_accuracy(state)\n",
        "\n",
        "        return Solution.solutions[Solution.str_sol(state)]\n",
        "\n",
        "    def get_state(self):\n",
        "        return copy.deepcopy(self.state)\n",
        "\n",
        "    def set_accuracy(self,state): \n",
        "        t1 = time.time()\n",
        "        Solution.solutions[Solution.str_sol(state)] = self.data.evaluate(state)\n",
        "        self.accuracy = Solution.solutions[Solution.str_sol(state)]\n",
        "        t2 = time.time()\n",
        "        Solution.tot_eval_time += t2-t1\n",
        "        if (Solution.best_sol == None) or (Solution.best_sol.get_accuracy(Solution.best_sol.get_state()) < self.accuracy):\n",
        "            Solution.best_sol = self\n",
        "    \n",
        "    def set_state(self,state): \n",
        "        self.state = copy.deepcopy(state)\n",
        "            \n",
        "    @staticmethod\n",
        "    def get_best_sol():\n",
        "      # This part has been changed by a variable \"best_sol\", because sorting was costing some execution time\n",
        "        \"\"\"t1 = time.time()\n",
        "        sorted_sols = sorted(Solution.solutions.items(), key=operator.itemgetter(1), reverse=True)\n",
        "        t2 = time.time()\n",
        "        #print(\"Best sol after sort : {0}\".format(sorted_sols[0][1]))\n",
        "        Solution.sorting_time += t2-t1\n",
        "        return sorted_sols[0][0] ,sorted_sols[0][1]\"\"\"\n",
        "        \n",
        "        best_state = Solution.best_sol.get_state()\n",
        "        best_accuracy = Solution.best_sol.get_accuracy(best_state)\n",
        "        return Solution.str_sol(best_state), best_accuracy\n",
        "\n",
        "      \n",
        "    @staticmethod\n",
        "    def get_indexes(mlist):\n",
        "        ilist = []\n",
        "        for i in range(len(mlist)):\n",
        "          if mlist[i] == 1:\n",
        "            ilist.append(i)\n",
        "        return ilist\n",
        "      \n",
        "    @staticmethod\n",
        "    def str_sol(mlist):\n",
        "        result = ''\n",
        "        for element in mlist:\n",
        "            result += str(element)\n",
        "        return result\n",
        "    \n",
        "    @staticmethod\n",
        "    def sol_to_list(solution):\n",
        "      sol_list=[i for i, n in enumerate(solution) if n == 1]\n",
        "      return sol_list\n",
        "    \n",
        "    @staticmethod\n",
        "    def list_sol(key):\n",
        "        mlist = [ int(i) for i in key ]\n",
        "        return mlist\n",
        "      \n",
        "    @staticmethod\n",
        "    def nbrUn(state):\n",
        "        return len([i for i, n in enumerate(state) if n == 1])\n",
        "    \n",
        "    @staticmethod\n",
        "    def attributs_to_flip(nb_att):\n",
        "        return list(range(nb_att))\n",
        "    \n",
        "    @staticmethod\n",
        "    def xor(x, y):\n",
        "        return '{1:0{0}b}'.format(len(x), int(Solution.str_sol(x), 2) ^ int(Solution.str_sol(y), 2))\n",
        "    \n",
        "    @staticmethod\n",
        "    def get_avg_time():\n",
        "      return Solution.tot_eval_time/len(Solution.solutions)\n",
        "    \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "No1rMDEhCEd5",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Reinforcement learning class\n",
        "This class containts the implementation of the different RL algorithms"
      ]
    },
    {
      "metadata": {
        "id": "fYWjrRN6-vP5",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class QLearning:\n",
        "    def __init__(self,nb_atts,actions):\n",
        "        self.actions = actions\n",
        "        self.alpha = 0.1\n",
        "        self.gamma = 0.9\n",
        "        self.epsilon = 0.1\n",
        "        self.q_table = [ {} for i in range(nb_atts) ] \n",
        "\n",
        "    def get_max_q_value(self,solution,actions_vals):\n",
        "        max_val = 0.0\n",
        "        arg_max = 0\n",
        "\n",
        "        for i in actions_vals: # Basic itirative max search from a list of possible actions\n",
        "            state_i = self.get_next_state(solution,i)\n",
        "            state_i_acc = solution.get_accuracy(state_i)\n",
        "            if state_i_acc > max_val: \n",
        "                max_val = self.get_q_value(solution,i) + state_i_acc\n",
        "                arg_max = i\n",
        "\n",
        "        return max_val, arg_max # We return the max q_value and the action that led to it from that state\n",
        "\n",
        "\n",
        "    def get_q_value(self,solution,action):\n",
        "        \n",
        "        state = solution.get_state()\n",
        "        if not Solution.str_sol(state) in self.q_table[Solution.nbrUn(state)]: \n",
        "            self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)] = {}\n",
        "\n",
        "        if not str(action) in self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)]:\n",
        "            # We initilize the q_table with 0\n",
        "            self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)][str(action)] = 0\n",
        "            \n",
        "        return self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)][str(action)]\n",
        "\n",
        "    \n",
        "    def set_q_value(self,solution,action,val):\n",
        "        state = solution.get_state()\n",
        "        self.q_table[Solution.nbrUn(state)][Solution.str_sol(state)][str(action)] = val\n",
        "\n",
        "    \n",
        "    def step(self,solution,actions,flip):\n",
        "        \n",
        "        if len(actions) != 0:\n",
        "          if len(actions) > flip:\n",
        "            self.actions = [actions[i] for i in sorted(random.sample(range(len(actions)), flip))]\n",
        "          else:\n",
        "            self.actions = [actions[i] for i in sorted(random.sample(range(len(actions)), 1))]\n",
        "        \n",
        "        if np.random.uniform() > self.epsilon :\n",
        "            \n",
        "            #action_values = [self.actions[i] for i in sorted(random.sample(range(len(self.actions)), sample_size))]\n",
        "            action_values = self.actions\n",
        "            max_val = self.get_max_q_value(solution,action_values)[0] # getting the max next q_value\n",
        "            argmax_actions=[self.get_max_q_value(solution,action_values)[1]] # saving the action that maxmizes the reward\n",
        "\n",
        "            # There may be actions that have the same reward, so we add them to the argmax_avtions\n",
        "            for ac in action_values : \n",
        "              ac_state = self.get_next_state(solution,ac)\n",
        "              ac_state_q_val = self.get_q_value(solution,ac) + solution.get_accuracy(ac_state)\n",
        "              \n",
        "              if ( ac_state_q_val >= max_val ):\n",
        "                  argmax_actions.append(ac) \n",
        "                  # We could make the condition \"equal\", because theorically there won't be any bigger q_value\n",
        "            next_action = np.random.choice(argmax_actions) # We choose a random action from eqaul reward actions\n",
        "            next_state = self.get_next_state(solution,next_action)\n",
        "\n",
        "        else : # This is the exploration condition\n",
        "            next_action = np.random.choice(self.actions)\n",
        "            next_state = self.get_next_state(solution,next_action)\n",
        "\n",
        "        if self.epsilon > 0 :\n",
        "            self.epsilon -= 0.0001 \n",
        "        if self.epsilon < 0 :\n",
        "            self.epsilon = 0\n",
        "\n",
        "        return next_state, next_action \n",
        "\n",
        "    def get_next_state(self,solution,action):\n",
        "        next_state = solution.get_state()\n",
        "        next_state[action] = (next_state[action]+1) % 2\n",
        "        if (Solution.nbrUn(next_state) != 0):\n",
        "          return next_state\n",
        "        else:\n",
        "          return solution.get_state()\n",
        "    \n",
        "    def learn(self,current_sol,current_action,reward,next_sol):\n",
        "        next_action = self.get_max_q_value(next_sol,self.actions)[1] # Get the action with the max reward\n",
        "        new_q = reward + self.gamma * self.get_q_value(next_sol,next_action)  #This part will be multiplied by alpha\n",
        "        self.set_q_value(current_sol,current_action,(1 - self.alpha)*self.get_q_value(current_sol,current_action) + self.alpha*new_q) # This is the basic Q-learning formula\n",
        "        \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "ozRRchjjCMpp",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Evaluation class\n",
        "This class contains the implementation of evaluation methods and could be extended to other problems than feature selection"
      ]
    },
    {
      "metadata": {
        "id": "1MknP4sm-ywr",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class FsProblem :\n",
        "    def __init__(self,typeOfAlgo,data,qlearn,classifier=KNeighborsClassifier(n_neighbors=1)):\n",
        "        self.data=data\n",
        "        self.nb_attribs = len(self.data.columns)-1 # The number of features is the size of the dataset - the 1 column of labels\n",
        "        self.outPuts=self.data.iloc[:,self.nb_attribs] # We initilize the labels from the last column of the dataset\n",
        "        self.ql = qlearn\n",
        "        self.classifier = classifier\n",
        "        self.typeOfAlgo = typeOfAlgo\n",
        "\n",
        "    def evaluate2(self,solution):\n",
        "        sol_list = Solution.sol_to_list(solution)\n",
        "        if (len(sol_list) == 0):\n",
        "            return 0\n",
        "         \n",
        "        df = self.data.iloc[:,sol_list]\n",
        "        array=df.values\n",
        "        X = array[:,0:self.nb_attribs]\n",
        "        Y = self.outPuts\n",
        "        train_X, test_X, train_y, test_y = train_test_split(X, Y, \n",
        "                                                    random_state=0,\n",
        "                                                    test_size=0.1\n",
        "                                                    )\n",
        "        self.classifier.fit(train_X,train_y)\n",
        "        predict= self.classifier.predict(test_X) \n",
        "        return metrics.accuracy_score(predict,test_y)\n",
        "\n",
        "\n",
        "    def evaluate(self,solution):\n",
        "        sol_list = Solution.sol_to_list(solution)\n",
        "        if (len(sol_list) == 0):\n",
        "            return 0\n",
        "        \n",
        "        df = self.data.iloc[:,sol_list] # For this function you need to put the indexes of features you picked  \n",
        "        array=df.values\n",
        "        X = array[:, 0:self.nb_attribs]\n",
        "        Y = self.outPuts\n",
        "        cv = ShuffleSplit(n_splits=10, test_size=0.1, random_state=0) # Cross validation function\n",
        "        results = cross_val_score(self.classifier, X, Y, cv=cv,scoring='accuracy')\n",
        "        #print(\"\\n[Cross validation results]\\n{0}\".format(results))\n",
        "        return results.mean()\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "ki1SQkESCdyV",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Data class\n",
        "This class is the one resbonsible for processing and getting the data ready to be trained"
      ]
    },
    {
      "metadata": {
        "id": "ekyU5LcV-12g",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class FSData():\n",
        "\n",
        "    def __init__(self,typeOfAlgo,location,nbr_exec):\n",
        "        \n",
        "        self.typeOfAlgo = typeOfAlgo\n",
        "        self.location = location\n",
        "        self.nb_exec = nbr_exec\n",
        "        self.dataset_name = re.search('[A-Za-z\\-]*.csv',self.location)[0].split('.')[0]\n",
        "        self.df = pd.read_csv(self.location,header=None)\n",
        "        self.ql = QLearning(len(self.df.columns),Solution.attributs_to_flip(len(self.df.columns)-1))\n",
        "        self.fsd = FsProblem(self.typeOfAlgo,self.df,self.ql)\n",
        "        \n",
        "        self.classifier_name = str(type(self.fsd.classifier)).strip('< > \\' class ').split('.')[3]\n",
        "        path = gdrive_path + '/My Drive/Colab Notebooks/results/'+ self.dataset_name\n",
        "        if not os.path.exists(path):\n",
        "          os.makedirs(path + '/logs/')\n",
        "          os.makedirs(path + '/sheets/')\n",
        "        self.instance_name = str(self.typeOfAlgo) + '-' + self.dataset_name + '_' +  str(time.strftime(\"%m-%d-%Y_%H-%M-%S_\", time.localtime()) + self.classifier_name)\n",
        "        log_filename = str(path + '/logs/'+ self.instance_name)\n",
        "        if not os.path.exists(path):\n",
        "          os.makedirs(path)\n",
        "        log_file = open(log_filename + '.txt','w+')\n",
        "        sys.stdout = log_file\n",
        "        \n",
        "        print(\"[START] Dataset \" + self.dataset_name + \" description \\n\")\n",
        "        print(\"Shape : \" + str(self.df.shape) + \"\\n\")\n",
        "        print(self.df.describe())\n",
        "        print(\"\\n[END] Dataset \" + self.dataset_name + \" description\\n\")\n",
        "        print(\"[START] Ressources specifications\\n\")\n",
        "        !cat /proc/cpuinfo # Think of changing this when using Windows\n",
        "        print(\"[END] Ressources specifications\\n\")\n",
        "\n",
        "        \n",
        "        sheet_filename = str(path + '/sheets/'+ self.instance_name )\n",
        "        self.workbook = xlsxwriter.Workbook(sheet_filename + '.xlsx')\n",
        "        \n",
        "        self.worksheet = self.workbook.add_worksheet(self.classifier_name)\n",
        "        self.worksheet.write(0,0,\"Iteration\")\n",
        "        self.worksheet.write(0,1,\"Accuracy\")\n",
        "        self.worksheet.write(0,2,\"N_Features\")\n",
        "        self.worksheet.write(0,3,\"Time\")\n",
        "        self.worksheet.write(0,4,\"Top_10%_features\")\n",
        "        self.worksheet.write(0,5,\"Size_sol_space\")\n",
        "\n",
        "    \n",
        "    def run(self,flip,maxChance,nbrBees,maxIterations,locIterations):\n",
        "        total_time = 0\n",
        "        \n",
        "        for itr in range(1,self.nb_exec+1):\n",
        "          print (\"Execution {0}\".format(str(itr)))\n",
        "          self.fsd = FsProblem(self.typeOfAlgo,self.df,self.ql)\n",
        "          swarm = Swarm(self.fsd,flip,maxChance,nbrBees,maxIterations,locIterations)\n",
        "          t1 = time.time()\n",
        "          best = swarm.bso(self.typeOfAlgo,flip)\n",
        "          t2 = time.time()\n",
        "          total_time += t2-t1\n",
        "          print(\"Time elapsed for execution {0} : {1:.2f} s\\n\".format(itr,t2-t1))\n",
        "          self.worksheet.write(itr, 0, itr)\n",
        "          self.worksheet.write(itr, 1, \"{0:.2f}\".format(best[0]))\n",
        "          self.worksheet.write(itr, 2, best[1])\n",
        "          self.worksheet.write(itr, 3, \"{0:.3f}\".format(t2-t1))\n",
        "          self.worksheet.write(itr, 4, \"{0}\".format(str([j[0] for j in [i for i in swarm.best_features()]])))\n",
        "          self.worksheet.write(itr, 5, len(Solution.solutions))\n",
        "          \n",
        "        print (\"Total execution time of {0} executions \\nfor dataset \\\"{1}\\\" is {2:.2f} s\".format(self.nb_exec,self.dataset_name,total_time))\n",
        "        self.workbook.close()\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "TDUcwNhHztw9",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Visualization class\n",
        "This class is responsible of plotting visuals out of input data."
      ]
    },
    {
      "metadata": {
        "id": "GTZtemxtz7Qu",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "\"\"\"class Plot:\n",
        "  def __init__(self,data_file):\"\"\""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "PbqnYZXyCoG_",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# The main program\n",
        "In the part you can specify the parameters' values.\n",
        "Those parameters are :\n",
        "\n",
        "\n",
        "*   **dataset** : the dataset name ( without **.cvs** extension ), from the list of [datasets](https://github.com/Neofly4023/bso-fs/tree/master/datasets), or you can put your own **.csv** dataset (without header row, and index column)\n",
        "*   **typeOfAlgo** : for now, the value is 0, for the original localsearch algorithm, or 1, for the q-localsearch algorithm\n",
        "*  **nbr_exec** : the number of executions\n",
        "*  **flip** : the flip parameter is used to generate solutions from the searchArea\n",
        "*  **maxChance** : the maxChance parameter is a used for exploitation\n",
        "*  **nbrBees** : the number of Bees used\n",
        "*  **maxIterations** : the number of iterations inside the BSO algorithm, it is possible to not reach it\n",
        "*  **locIterations** : the number of iterations inside the localsearch algorithms (orginal & q-learning)\n",
        "\n",
        "For more details, please check the previous [work](https://link.springer.com/chapter/10.1007%2F978-3-319-19258-1_33), or PM me via : [e-mail](mailto:ea_remache@esi.dz)"
      ]
    },
    {
      "metadata": {
        "id": "GeFvyPenG1FN",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Main program\n",
        "\n",
        "# Prepare the dataset\n",
        "\n",
        "dataset = \"WaveformEW\"\n",
        "data_loc_path = \"https://raw.githubusercontent.com/Neofly4023/bso-fs/master/datasets/\"\n",
        "location = data_loc_path + dataset + \".csv\"\n",
        "\n",
        "# Params init\n",
        "\n",
        "typeOfAlgo = 0\n",
        "nbr_exec = 1\n",
        "flip = 5\n",
        "maxChance = 3\n",
        "nbrBees = 10\n",
        "maxIterations = 10\n",
        "locIterations = 10\n",
        "\n",
        "instance = FSData(typeOfAlgo,location,nbr_exec)\n",
        "instance.run(flip,maxChance,nbrBees,maxIterations,locIterations)"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}